// https://www.lintcode.com/problem/add-binary/

public class Solution {
    /**
     * @param a: a number
     * @param b: a number
     * @return: the result
     */
    public String addBinary(String a, String b) {
        // write your code here
        StringBuilder sb = new StringBuilder();
        int step = 0;
        int l_a = a.length() - 1, l_b = b.length() - 1;
        while ((l_a >= 0) && (l_b >= 0)) {
            int v = (a.charAt(l_a) - '0') + (b.charAt(l_b) - '0') + step;
            step = (v >= 2) ? 1 : 0;
            v %= 2;
            sb.append(v); // 自动映射成字符串
            --l_a;
            --l_b;
        }
        int l = (l_a >= 0) ? l_a : l_b;
        String s = (l_a >= 0) ? a : b;
        while (l >= 0) {
            int v = (s.charAt(l) - '0') + step;
            step = (v >= 2) ? 1 : 0;
            v %= 2;
            sb.append(v); // 自动映射成字符串
            --l;
        }
        if (step > 0) {
            sb.append(step);
        }
        sb.reverse();
        return sb.toString();
    }
}